package everyday3;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-07-13-10:46
 * @Description: 1.0
 */
public class T1573 {
    public int numWays(String s) {
        final int M = 1000000007;
        char[] chars = s.toCharArray();
        int n = chars.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (chars[i] == '1') {
                list.add(i);
            }
        }
        int sum = list.size();
        if (sum % 3 != 0) return 0;
        if (sum == 0) return (int) (((long) (n - 1) * (n - 2) / 2) % M);
        int count1 = list.get(sum / 3) - list.get(sum / 3 - 1);
        int count2 = list.get(sum / 3 * 2) - list.get(sum / 3 * 2 - 1);
        return (int) (((long) count1 * count2) % M);
    }
}
